1. Field of the Invention
The present invention generally relates to the high data rate (HDR) system, and particularly, to a forward channel scheduling algorithm realized in an HDR system.
2. Background of the Related Art
A high data rate (HDR) system is a third-generation mobile communication system for providing a high-rate packet data service, excluding real-time voice service. Some trials for providing real-time services such as video telephone and VOD have been attempted on HDR systems currently in use, and some service providers are actually providing VOD service on HDR systems already.
A forward channel of the HDR system uses a time division multiple access (TDMA) method. The TDMA method divides time into predetermined intervals (slots), and allots each slot to mobile terminals to provide a plurality of mobile terminals with services. At that time, a base station uses a scheduling algorithm to select the mobile terminal to be served at each respective slot. The HDR system obtains data rate control (DRC) information from the mobile terminal which is presently served, and uses the above information for the scheduling algorithm. The DRC information is a parameter representing the data transmission rate that can be served to the mobile terminal from the base station through the forward channel.
VOD or video phone services should be provided in teal-time, unlike general data services which are not limited to time. In addition, VOD and video phone services should be ensured for high Quality of Service (QoS) from the HDR system. Representative QoS parameters include maximum allowable time delay (T) and packet loss tolerance probability (δ). Maximum allowable time delay (T) means the delayed time that is allowed in transmitting packets, and packet loss tolerance probability (δ) is the probability that a packet is allowed to be lost.
Packet loss mainly occurs when the packet transmission time is longer than the maximum allowable time delay (T), or occurs due to radio channel error. In the case of voice telephoning, the maximum allowable time delay is about 25 ms, and the packet loss tolerance probability is 10−3. In the case of video telephones, the time delay is allowed to be hundreds of ms, however the packet loss tolerance probability is about 10−5.
On the other hand, general data services such as web service or e-mail service allows for a time delay of about a few seconds to tens of seconds. However, the packet loss tolerance probability is very small, that is, about 10−9.
HDR systems which provide the aforementioned services require an effective scheduling algorithm in order to improve the throughput of the system and to therefore maintain a certain service quality of each user.
FIG. 1 is a flow chart showing a related-art scheduling algorithm, and Equation (1) is an equation for calculating priority (P) according to the related-art algorithm.
                              P          j                =                              (                                          -                log                            ⁢                                                          ⁢                              δ                i                                      )                    ×                                                    D                i                            ⁡                              (                t                )                                                                                      D                  _                                i                            ⁡                              (                t                )                                              ×                                                    W                i                            ⁡                              (                t                )                                                    T              i                                                          (        1        )            In Equation (1), Ti is the maximum allowable time delay of a mobile terminal i, and δi is the probability of tolerating violation in the time delay (Ti).
A control unit which performs the related-art scheduling algorithm receives DRC information in every slot from all mobile terminals (S10). DRC information received from mobile terminal i is represented as Di(t). Based on the received DRC information, the average data transmission rate ( Di(t)) is calculated (S11). In FIG. 1, D*i(t) is the data transmission rate of mobile terminal i in slot t, and the Di(t) is the average packet transmission rates from the first slot to (t-1)th slot. Next, the delayed time Wi(t) of the first packet in the queue dedicated to the mobile terminal i is calculated (S12). The first packet of the queue is the packet having the longest delayed time, and the delayed time can be obtained by calculating the difference between the present time and the arrival time of the packet.
As described above, when the components required in Equation (1) are all obtained, the control unit uses Equation (1) to calculate the priority values of the respective mobile terminals (S13). More specifically, Equation (1) multiplies the inverse proportion component (−log δi) of the time delay violation tolerance probability δI, a comparative component (Di(t)/ Di(t)) of the average data transmission rate and the DRC information of the corresponding mobile terminal, and the comparative component (Wi(t)/Ti) between the maximum allowable time delay Ti of the packet and the present delayed time Wi(t).
When the priority values of the respective mobile terminals are obtained, the control unit serves the packets of the mobile terminal having the highest priority (S14).
In view of the first component (−log δi) of Equation (1), the priority of the terminal increases as the δi becomes smaller; thus, P is inversely proportional with δi. Also, the first component (−log δi) maintains balance of the time delay violation tolerance probability δi. That is, if it is assumed that values of the second component (Di(t)/ Di(t)) and the third component (Wi(t)/Ti) are fixed, the priority value of the corresponding mobile terminal is increased and the time delay violation is lowered as the δ becomes smaller, and therefore, the QoS of the user can be satisfied.
The second component (Di(t)/ Di(t)) in the Equation (1) affects the decision of service priority value, by comparing the DRC information representing the radio channel status to the served average data rate. That is, the service is frequently provided to the mobile terminal having a radio channel which is in good condition, to improve the entire throughput of the HDR system.
The third component (Wi(t)/Ti) of Equation (1) affects the decision of service priority value, by comparing the maximum allowable time delay Ti of the packet and the presently delayed time Wi(t). That is, higher priority is provided to the packet of the mobile terminal having a long presently delayed time Wi(t) (or the packet having relatively longer delayed time).
As described above, the related-art scheduling algorithm provides service to the mobile terminal having a small time delay violation tolerance probability (δ), to the mobile terminal having a radio channel of higher condition than that of the average service rate and to the mobile terminal suffering relatively long time delay.
A significant disadvantage of the related-art scheduling algorithm is that it does not consider the number of mobile terminals connected to the HDR system. In the related-art algorithm, the first component (−log δi) and the third component (Wi(t)/Ti) are related to service quality, and they are determined independently of the number of mobile terminals. But, the second component (Di(t)/ Di(t)) is affected by the number of mobile terminals. Di(t) is the value affected by the property of radio channel, and is not changed according to the number of mobile terminals. However, Di(t) is reduced as the number of mobile terminals is increased, because a lot of mobile terminals share the limited bandwidth of the system.
Consequently, in the related-art algorithm, when the number of mobile terminals increases, the effect of the first component (−log δi) and the third component (Wi(t)/Ti) is reduced since the second component (Di(t), Di(t)) becomes more dominant than the other two components in Equation (1). This means that the first and third components have little effect on the determination of the mobile terminal whose packet will be served in the next time slot. As a result, the QoS requirements of the mobile terminals cannot be satisfied.